package com.jjlin.chapter_3;
import java.util.*;

public class CD161{
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static Node createBinaryTree(int[][] nums, int root){
        HashMap<Integer, Node> map = new HashMap<>();
        int rows = nums.length;
        int cols = nums[0].length;
        for(int i = 0; i < rows; i++)
            for(int j = 0; j < cols; j++)
                if(nums[i][j] != 0 && !map.containsKey(nums[i][j]))
                    map.put(nums[i][j], new Node(nums[i][j]));

        for(int i = 0; i < rows; i++){
            Node node = map.get(nums[i][0]);
            if(nums[i][1] != 0)
                node.left = map.get(nums[i][1]);
            if(nums[i][2] != 0)
                node.right = map.get(nums[i][2]);
        }
        return map.get(root);
    }

    //先序遍历
    public static void preOrderRecur(Node head){
        if(head == null)
            return;
        System.out.print(head.val + " ");
        preOrderRecur(head.left);
        preOrderRecur(head.right);
    }

    //中序遍历
    public static void inOrderRecur(Node head){
        if(head == null)
            return;
        inOrderRecur(head.left);
        System.out.print(head.val + " ");
        inOrderRecur(head.right);
    }

    //后序遍历
    public static void posOrderRecur(Node head){
        if(head == null)
            return;
        posOrderRecur(head.left);
        posOrderRecur(head.right);
        System.out.print(head.val + " ");
    }

    //先序遍历(非递归)
    public static void preOrederUnRecur(Node head){
        if(head == null)
            return;
        Stack<Node> stack = new Stack<>();
        stack.add(head);
        while(!stack.isEmpty()){
            Node node = stack.pop();
            System.out.print(node.val + " ");
            if(node.right != null)
                stack.add(node.right);
            if(node.left != null)
                stack.add(node.left);
        }
    }

    //中序遍历(非递归)
    public static void inOrderUnRecur(Node head){
        if(head == null)
            return;
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while(!stack.isEmpty() || cur != null){
            if(cur != null){
                stack.add(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }

    //后序遍历(非递归)
    public static void posOrderUnRecur(Node head){
        if(head == null)
            return;
        Stack<Node> s1 = new Stack<>();
        Stack<Node> s2 = new Stack<>();
        s1.push(head);
        while(!s1.isEmpty()){
            Node node = s1.pop();
            s2.push(node);
            if(node.left != null)
                s1.push(node.left);
            if(node.right != null)
                s1.push(node.right);
        }
        while(!s2.isEmpty())
            System.out.print(s2.pop().val + " ");
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < 3; j++)
                nums[i][j] = sc.nextInt();
        Node head = createBinaryTree(nums, root);
//         preOrderRecur(head);
        preOrederUnRecur(head);
        System.out.println();
//         inOrderRecur(head);
        inOrderUnRecur(head);
        System.out.println();
//         posOrderRecur(head);
        posOrderUnRecur(head);
        System.out.println();
    }
}
